home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1993…ch: Other People's Memory / ADC Developer CD (1993-03) (''Other People's Memory'')_iso / Dev.CD Mar 93.iso / Development Platforms / LISP Related / LISP Goodies / btree / btree-dcl.lisp < prev    next >
Encoding:
Text File  |  1992-09-02  |  2.5 KB  |  79 lines  |  [TEXT/CCL2]
  1. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  2. ;; btree-dcl.lisp
  3. ;;
  4. ;; Copyright © 1992 University of Toronto, Department of Computer Science
  5. ;; All Rights Reserved
  6. ;;
  7. ; author: Mark A. Tapia markt@dgp.toronto.edu or markt@dgp.utoronto.ca
  8. ;; 
  9. ;; declarations for btrees
  10. ;;
  11.  
  12. (in-package btree)
  13. (provide 'btree-decl)
  14. (export '(*before* *after* *equal*
  15.           *left* *right* *done*
  16.           *left-taller* *right-taller* *balanced*
  17.           make-btree
  18.           btree-left
  19.           btree-right
  20.           btree-min
  21.           btree-max
  22.           btree-key
  23.           btree-val
  24.           btree-balance
  25.           make-btrail
  26.           btrail-dir
  27.           btrail-node
  28.           btrail-prev))
  29.  
  30. (defconstant *before* -1 "first key is before second")
  31. (defconstant *after* 1 "first key is after second")
  32. (defconstant *equal* 0 "first key equals second")
  33.  
  34. (defconstant *left* *before* "turn left")
  35. (defconstant *right* *after* "turn right")
  36. (defconstant *done* -2 "node already visited")
  37.  
  38.  
  39. (defconstant *balanced* 0 "tree is balanced")
  40. (defconstant *left-taller* -1 "left branches are taller")
  41. (defconstant *right-taller* +1 "right branches are taller")
  42.  
  43. ;; standard btree structure
  44. ;;   left       pointer to the left branch of the rooted subtree
  45. ;;   right      pointer to the right branch of the rooted subtree
  46. ;;   key        a pointer to the key of the rooted subtree
  47. ;;   val        value associated with the key
  48. ;;   min        if left then pointer to the leftmost node
  49. ;;              else nil
  50. ;;   min        if right then pointer to the right-most node
  51. ;;              else nil
  52. ;;   balance    one of *left-taller* *right-taller* *balanced*
  53. ;;              which satistfy *left-taller* + *right-taller* = *balanced* = 0
  54.  
  55. (defstruct (btree (:type list))
  56.   min left key val right max (balance *balanced*))
  57.  
  58. ;; a path is a list of any number of btrail structures
  59. ;;  ((dir-1 node-1) ... (dir-n node-n))
  60. ;; The path indicates the nodes visited (in reverse order) from the root to the first node
  61. ;;  if the node with the key is not found
  62. ;;        dir  = nil 
  63. ;;        node = key
  64. ;;        prev = direction of the turn from the last node visited on the path
  65. ;;               (btrail-dir node-2)
  66. ;;  otherwise 
  67. ;;        dir = one of *equal* *right* *left*
  68. ;;              indicating no turn, or a right or left turn to the previous node
  69. ;;        node = a btree structure
  70. ;;        prev = nil
  71. ;;  The root of the tree is the last node in the list.
  72.  
  73. (defstruct (btrail (:type list)) dir node prev)
  74.  
  75.  
  76.  
  77.  
  78.  
  79.